/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/7
 * \* Time: 17:54
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 完全二叉树的节点个数 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    public int countNodes(TreeNode root) {
        if(root==null){
            return 0;
        }
        //分别计算左右子树高度
        int left=countLevel(root.left);
        int right=countLevel(root.right);
        //如果左右子树高度相等则左子树一定是满二叉树left == right。
        // 这说明，左子树一定是满二叉树，因为节点已经填充到右子树了，左子树必定已经填满了。
        // 所以左子树的节点总数我们可以直接得到，是 2^left - 1，加上当前这个 root 节点，则正好是 2^left。再对右子树进行递归统计。
        //left != right。说明此时最后一层不满，但倒数第二层已经满了，可以直接得到右子树的节点个数。
        // 同理，右子树节点 +root 节点，总数为 2^right。再对左子树进行递归查找。

        if(left==right){
            return countNodes(root.right) + (1<<left);
        }else{
            return countNodes(root.left) + (1<<right);
        }
    }

    private int countLevel(TreeNode node){
        int level=0;
        while (node!=null){
            level++;
            node=node.left;
        }
        return level;
    }
}